package com.lwl.Algorithmic_data_structure.class12二叉树;

import com.lwl.Utils.MyTreeNode;

/**
 * @author lwl
 * @Description 判断是否平衡二叉树（每棵树的左右子树高度差不大于1）
 * @date 2023/5/31 22:43
 */
public class Code02isBalanceBT {

    class Info {

        boolean isBalance;

        int height;

        public Info(boolean isBalance, int height) {
            this.isBalance = isBalance;
            this.height = height;
        }
    }

    public boolean isBalanceBT(MyTreeNode treeNode) {
        return process(treeNode).isBalance;
    }

    public Info process(MyTreeNode treeNode) {
        // base case
        if (treeNode == null) {
            return new Info(true, 0);
        }

        Info leftInfo = process(treeNode.left);
        Info rightInfo = process(treeNode.right);

        boolean isBalance = (Math.abs(leftInfo.height - rightInfo.height) <= 1) & leftInfo.isBalance & rightInfo.isBalance;
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        return new Info(isBalance, height);
    }
}
